package com.company.graph;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class 克隆图 {

    public Node cloneGraph(Node node) {
        if (node == null) return null;
        Queue<Node> queue = new LinkedList<>();
        HashMap<Node,Node> visited = new HashMap<>();

        queue.offer(node);
        visited.put(node,new Node(node.val));
        while (! queue.isEmpty()) {
            Node thisNode = queue.poll();

            for (Node neighbor : thisNode.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited.put(neighbor,new Node(neighbor.val));
                    queue.offer(neighbor);
                }
                visited.get(thisNode).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }

}
